//
// Created by aaa on 2025/7/11.
//

#include<bits/stdc++.h>

using namespace std;
const int N = 1e3 + 10;

int n,m;
int w[N],v[N];
int dp[N];
//完全背包
//4 5
//1 2
//2 4
//3 4
//4 5
int main(){
    cin >> n >> m;

    for(int i = 1;i <= n;i++) cin >> w[i] >> v[i];

//    for(int i = 1;i <= n;i++){
//        for(int j = 1;j <= m;j++){
//            if(w[i] > j) dp[i][j] = dp[i-1][j];
//            else dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
//        }
//    }

//    for(int i = 1;i <= n;i++){
//        for(int j = 1;j <= m;j++){
//            cout << dp[i][j] << " ";
//        }
//        cout << endl;
//    }

//    cout << dp[n][m];

    for(int i = 1;i <= n;i++){
        for(int j = w[i];j <= m;j++){
            dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[m];


    return 0;
}